import java.util.Scanner;

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class MergeAndReverse {
    public static void main(String[] args) {
        // 输入链表1
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入 链表1 的结点个数:");
        int n1 = scanner.nextInt();
        Node list1 = createList(1, n1, scanner);

        // 输入链表2
        System.out.print("请输入 链表2 的结点个数:");
        int n2 = scanner.nextInt();
        Node list2 = createList(2, n2, scanner);

        // 打印输入链表
        System.out.println("\n链表1：" + printList(list1));
        System.out.println("链表2：" + printList(list2));

        // 合并链表
        Node merged = mergeSortedLists(list1, list2);
        System.out.println("合并链表1和链表2：" + printList(merged));

        // 反转链表
        Node reversed = reverseList(merged);
        System.out.println("合并链表1和链表2并将其逆序：" + printList(reversed));
    }

    // 创建有序链表
    private static Node createList(int listNum, int count, Scanner scanner) {
        Node dummy = new Node(-1);
        Node current = dummy;

        for (int i = 0; i < count; i++) {
            System.out.printf("请输入 链表%d 的第 %d 个结点的值:", listNum, i+1);
            int val = scanner.nextInt();
            current.next = new Node(val);
            current = current.next;
        }
        return dummy.next;
    }

    // 合并两个有序链表
    private static Node mergeSortedLists(Node l1, Node l2) {
        Node dummy = new Node(-1);
        Node current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.data <= l2.data) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    // 反转链表
    private static Node reverseList(Node head) {
        Node prev = null;
        while (head != null) {
            Node next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    // 格式化输出链表
    private static String printList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.data);
            if (head.next != null) sb.append("->");
            head = head.next;
        }
        return sb.append("->nullptr").toString();
    }
}